def get_largest_neighbour(graph):
    """If there is a tie, it will return the first one it finds."""
    max_key = None
    max_length = 0

    for key, edges in graph.items():
        if len(edges) > max_length:
            max_length = len(edges)
            max_key = key

    return max_key


def get_edges(graph):
    unique_values = set()

    for node, edges in graph.items():
        unique_values.update(edges)

    return sorted(list(unique_values))


def check_colouring(graph, node_colours):
    edges = get_edges(graph)
    success = True
    for current in edges:
        nodes = list(current)
        if node_colours.get(nodes[0]) == node_colours.get(nodes[1]):
            success = False

    return success


def find_colouration(graph):
    vertices = list(graph.keys())
    largest_neighbour = get_largest_neighbour(graph)
    max_neighbours = graph.get(largest_neighbour, "")
    d_neighbours = len(max_neighbours)
    k_number = 1 + d_neighbours

    node_colours = {key: None for key in graph}
    possible_colours = list(range(1, k_number + 1))
    available_colours = {key: possible_colours[:] for key in graph}
    for vertex in vertices:  # each node in the graph
        pop_colour = available_colours[vertex].pop()
        node_colours[vertex] = pop_colour
        edges = graph.get(vertex)
        for current in edges:  # each neighbour
            nodes = list(current)
            # each node in the edge; will always be just 2
            for node in nodes:
                if pop_colour in available_colours[node]:
                    available_colours[node].remove(pop_colour)

    return node_colours, k_number, d_neighbours


# def colour_clock(clock, count):
#     time = count % clock
#     return clock if time == 0 else time


# def find_colouration_alt1(graph):
#     # vertices = list(graph.keys())  # not using
#     edges = get_edges(graph)
#     largest_neighbour = get_largest_neighbour(graph)
#     max_neighbours = graph.get(largest_neighbour, "")
#     d_neighbours = len(max_neighbours)
#     k_number = 1 + d_neighbours

#     colour_count = 0
#     node_colours = {key: None for key in graph}
#     for current in edges:
#         nodes = list(current)
#         if node_colours.get(nodes[0]) is None:
#             node_colours[nodes[0]] = colour_clock(
#                 clock=k_number,
#                 count=colour_count,
#             )
#             colour_count = colour_count + 1
#         if node_colours.get(nodes[1]) is None:
#             node_colours[nodes[1]] = colour_clock(
#                 clock=k_number,
#                 count=colour_count,
#             )
#             colour_count = colour_count + 1
#         if node_colours.get(nodes[0]) == node_colours.get(nodes[1]):
#             """This is either an edge case or it won't happen at all."""
#             node_colours[nodes[1]] = colour_clock(
#                 clock=k_number,
#                 count=colour_count,
#             )
#             colour_count = colour_count + 1

#     return node_colours, k_number, d_neighbours
